import java.util.*;
public class Text {
    //给定两个字符串 S 和 T ，判断 S 是否是 T 的子序列。
    //即是否可以从 T 删除一些字符转换成 S。
    //T 删掉一些字符变成 S
    //不要从 T 中拿跟 S 一样的字符，而是删掉 T 中 S 没有的字符
    public boolean isSubsequence (String S, String T) {
        int i = 0;
        int j = 0;
        while(i < S.length() && j < T.length()){
            if(S.charAt(i) == T.charAt(j)){
                i++;
                j++;
            }else{
                j++;
            }
        }
        return i == S.length();
    }

    //把字符串中相邻两个相同字母消除，例如，字符串"abbc"点击后可以生成"ac"。
    //但相同而不相邻、不相同的相邻字母都是不可以被消除的。
    //一个字符串，仅由小写字母组成。
    //若最终的字符串为空串，则输出0。
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            Deque<Character> stack = new LinkedList<>();
            Deque<Character> stack1 = new LinkedList<>();
            for(int i = 0; i < str.length(); i++){
                if(stack.isEmpty() || stack.peek() != str.charAt(i)){
                    stack.push(str.charAt(i));
                }else{
                    stack.pop();
                }
            }
            if(stack.isEmpty()){
                System.out.print(0);
            }else{
                while(!stack.isEmpty()){
                    stack1.push(stack.pop());
                }

                while(!stack1.isEmpty()){
                    System.out.print(stack1.pop());
                }
            }
        }
    }

    //给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
    //
    //子数组 是数组中的一个连续部分。
    //方法1 ：
    //自己写的
    //如果数组很大，将会超出时间限制：
    public static int maxSubArray1(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for(int i = 0; i < nums.length; i++){
            int sum = 0;
            for(int j = i; j < nums.length; j++){
                sum += nums[j];
                set.add(sum);
            }
        }

        //2.创建一个TreeSet的排序器;
        TreeSet<Integer> set1 = new TreeSet<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer t1, Integer t2) {
                //t1.compareTo(t2)  是从小到大正序排序,同理t2 . t1 就是倒序排序;
                return t1.compareTo(t2);
            }
        });

        //3.将添加好数据的无序Set添加到TreeSet集合中去;
        set1.addAll(set);

        return set1.last();
    }

    public int maxSubArray(int[] nums) {
        int pre = 0;
        int maxAns = nums[0];
        for(int i = 0; i < nums.length; i++){
            pre = Math.max(pre + nums[i] ,nums[i]);
            maxAns = Math.max(pre,maxAns);
        }
        return maxAns;
    }

    public static void main2(String[] args) {
        int[] arr = {-2,1,-3,4,-1,2,1,-5,4};
        int ret = maxSubArray1(arr);
        System.out.println(ret);
    }

    //盛最多水的容器中
    //自己想到的方法：遍历所有宽度所得到的容器体积，结果 还是时间超标了
    public static int maxArea1(int[] height) {
        int n = height.length - 1;
        int max = 0;
        while(n > 0){
            for(int i = 0; i + n < height.length; i++){
                int min = height[i] <= height[i + n] ? height[i] : height[i + n];
                if(min * n > max){
                    max = min * n;
                }
            }
            n--;
        }
        return max;
    }

    //利用双指针，只需遍历一次数组，时间复杂度为 O(n)
    //指向短板的指针向内移动，而指向长版的指针不动。
        public static int maxArea(int[] height) {
            int left = 0 ;
            int right  = height.length - 1;
            int max= 0;
            while(left < right){
                int area = Math.min(height[left],height[right]) * (right - left);
                if(area > max){
                    max = area;
                }
                if(height[left] >= height[right]){
                    right--;
                }else{
                    left++;
                }
            }
            return max;
        }

    public static void main3(String[] args) {
        int[] arr = {1,8,6,2,5,4,8,3,7,9};
        int ret = maxArea(arr);
        System.out.println(ret);
    }

    //将罗马数字转换成整数
    //没想出来，看的答案：如果相邻的左罗马数字比右罗马数字小，那么这个左罗马数字对应的阿拉伯数字为负数，反之为正数
    //将这些罗马数字对应的正负数加起来，就是想要的 阿拉伯数字！！！
    public int romanToInt(String s) {
        int sum = 0;
        int i = 0 ;
        for(; i < s.length() - 1;i++){
            char ch = s.charAt(i);
            char ch1 = s.charAt(i + 1);
            if(getValue(ch) < getValue(ch1)){
                sum -= getValue(ch);
            }else{
                sum += getValue(ch);
            }
        }
        sum += getValue(s.charAt(i));
        return sum;
    }

    private int getValue(char ch){
        int num = 0;
        switch (ch){
            case 'I':
                num = 1;
                break;
            case 'V':
                num = 5;
                break;
            case 'X':
                num = 10;
                break;
            case 'L':
                num = 50;
                break;
            case 'C':
                num = 100;
                break;
            case 'D':
                num = 500;
                break;
            case 'M':
                num = 1000;
                break;
        }
        return num;

    }
}
